Subject: On the programming language `GAP'

Dear GAP-forum,

being an enthusiastic GAP user and programmer, I have
collected two suggestions on improving the GAP
language itself. Although I appreciate the idea of
`lean' languages, as for example GAP is, it seems
to me that GAP might benefit from these additions.
Especially ZF-comprehensions turned out to be so useful in
other languages I used before (Gofer, Haskell) that
I would be very glad to have it in GAP, too. In case these
ideas fit the general design considerations and
development strategy of the GAP-project I would
like to do actual implementation work on it.
Best regards,
Sebastian Egner.

1. ZF-comprehensions for lists and sets.
----------------------------------------

A Zermelo-Fraenkel-comprehension (ZF-c.) is a compact notation to
denote a collection (list or set) of objects. It resembles the
standard mathematical notation for comprehensions. An examples is

[ x^2 | for x in [100, 99 .. 1], IsPrime(x) ],

the list of squares of the primes not exceeding 100 in decending order.
Which could be written in GAP for example as

List(Filtered([100, 99 .. 1], IsPrime), x -> x^2)

or explicitly (not working as printed; name the function) as

( function ()
    local result, x;

    result := [];
    for x in [100, 99 .. 1] do
      if IsPrime(x) then
        Add(result, x^2);
      fi;
    od;
    return result;
  end
)()

Another example containing two generators ('for') yielding a set is

{ [n, r] | for n in [1..10], for r in PrimeResidues(n) },

the set of all pairs [n, r] being relative prime where 1 <= n <= 10.
This might be written in GAP as

Union(List([1..10], n -> List(PrimeResidues(n), r -> [n, r]))).

or explicitly (not working, too) as

( function ()
    local result, n, r;

    result := Set([]);
    for n in [1..10] do
      for r in PrimeResidues(n) do
        AddSet(result, [n, r]);
      od;
    od;
    return result;
  end
)()

The general ingrediences of a ZF-comprehension are
* iterators to loop formal variables (`x', `n', `r') over
structured homogeneous collections of objects (`[100, 99 .. 1]',
`[1..10]', `PrimeResidues(n)'),
* predicates to filter objects (`IsPrime(x)'), and
* collectors to form the resulting homogeneous collection
(`[ .. ]' and `{ .. }').

ZF-comprehensions do not add expressive power to the
GAP-language since they can always be replaced by expressions
in List(), Filtered(), Concatenation(), and Union().
However, they are very intuitive to read and write,
especially on the interactive input line. The implementation
has to be done in the underlying C-kernel since ZF-comprehensions
introduce a syntactic structures and set up a binding context
for the formal variables being used within the comprehension.
The syntactic expressions do not interfere with any other
existing structure, so old GAP-programs remain correct.

2. User-supplied iterators to run over structured objects
---------------------------------------------------------

The `for'-statement of GAP v3.x does only run over lists.
This implies that every time you iterate over the elements
of a structured object (like a group) the list of its
elements is formed before the iteration starts at all.
There is a particularly elegant way to extend the semantics
of the `for'-statement to run over structured objects:

The structured object obj has two additional fields in
its operations record to hold functions to do the iteration.
Namely an iterator record is produced by iter := newIterator(obj)
before the iteration begins. This record holds at least
the field iter.isEmpty containing a boolean value to indicate
if there is still an element to enumerate. While this flag
is false stepIterator(iter) modifies the iterator record
and sets iter.element to the current element.
The `for'-statement is augmented to recognize the case of
obj being no list but a record with an operations
field in which the two functions are available. In other words

obj := rec(
..special data of the object..
operations := rec(
newIterator := function (obj) .. return iter; end, # custom-made
stepIterator := function (iter) .. return; end, # dito.
..more operations for the object..
)
);

so the iteration

for x in obj do
..statements..
od;

is unrolled to mean something like

local iter;

iter := obj.operations.newIterator(obj);
while not iter.isEmpty do
obj.operations.stepIterator(iter);
x := iter.element;
..statements..
od;

This feature can be implemented in the GAP-language itself
but it will be most useful if the C-kernel is modified to
augment the `for'-statement --- especially in conjunction
with ZF-comprehensions. Namely `for' needs to set up a local
variable to hold the iterator. (Which must *not* be stored
in obj.) Note that the modification of the GAP-language is
limited to the `for'-statement, does not interfere with
the existing semantics of `for', and the feature does not
rely on peculiarities of any particular GAP-domain.